The present invention relates to the Fast Fourier Transform (FFT), and more particularly to accomplishing a FFT with a cyclic shift of the input data, or equivalently a FFT with a rotation of each output data.
The FFT has an enormous number of applications in modem digital signal processing, ranging from low-level telecommunication signaling to speech and image processing. In some applications, the transform data set is pre-shifted or post-rotated for specific purposes.
From transform theory, it is known that pre-shifting and post-rotation are equivalent operations. However, in conventional arrangements their implementations differ from one another. A pre-shifter is composed of a buffer at least the size of the transform size, and some addressing logic. By contrast, the post-rotator is implemented as a complex multiplier or as a pure rotator, using for example the COordinate Rotation DIgital Computer (CORDIC) algorithm, and some rotation angle generator (e.g., a table stored in a memory).
A typical application in which pre-shifting and/or post-rotation are used in conjunction with an FFT is in communication systems that utilize Orthogonal Frequency Division Multiplexing (OFDM) to communicate information. To date, OFDM is used in various wireless local area network (WLAN) standards (e.g., IEEE 802.11a and WiMAX) and digital television (DVB). OFDM is also being considered for future communication standards such as ultra wideband (UWB) and enhancements to the “3G” (third generation) cellular systems.
One use of the pre-shifting is in improving time synchronization in OFDM. A single time domain OFDM symbol with a cyclic prefix is illustrated in FIG. 1. At the transmitter, data is encoded into complex numbers, which are inverse Fourier transformed and appended with a cyclic prefix in the time domain. At the receiver side, data is recovered by applying the forward Fourier transform. Most, if not all, implementations rely on some FFT algorithm for the time-frequency transformations.
Receiver time synchronization, that is, finding the best location for placement of the FFT window, is crucial to achieve good receiver performance. Under no circumstances may the window be placed such that more than one symbol (including its cyclic prefix) is covered, since this would lead to inter-symbol interference (ISI), that is, the mixing of two independent symbols into one.
The optimal location of the window is to place it “as late as possible” without including data from the next symbol's cyclic prefix. An overly aggressive approach may, however, lead to ISI, so there has to be some margin of safety. Placing the window early, including parts of the cyclic prefix eliminates the risk of ISI, as long as the channel's impulse response is sufficiently short.
An early placement of the FFT window corresponds to a cyclic shift of the transform input data (see FIG. 1). The data chunk that was at the rightmost position in the transmitter now appears to the left in the receiver FFT window. For a system that uses frequency interpolation in the channel estimator, the larger the shift, the more complicated the interpolator. To keep the channel estimation simple, input data should be aligned in the FFT window by a pre-shift or post-rotation.
Another use for the pre-shifting and/or post-rotation in OFDM is when the communication channel has a large delay spread. Such channels experience a rotation in the frequency domain, which can be mitigated by the proposed FFT scheme.
The benefits of pre-shifting and/or post-rotation do not come without a price. A circular shift in the time domain requires a large buffer and a corresponding latency and energy consumption for a hardware implementation. The corresponding post-rotation requires a high precision de-rotator operating on all transform output data, resulting in an increase in chip area as well as energy consumption.
Existing solutions have presented problems. The state-of-the-art circular shift is implemented either in the time domain or the frequency domain. Although the two methods result in different realizations, what they have in common is that area, latency, and energy consumption increase to a significant amount compared to the FFT alone.
For a time domain solution, the input data to the FFT is shifted circularly before transformation. In order to perform this shift, all data to be transformed must be available if the FFT is not implemented using a pipelined approach. Thus an extra buffer of size N words is needed. Even if a pipelined approach is used for the FFT, it may be necessary to provide a buffer to store as many as N-1 words, depending on the amount of circular shifting that the arrangement is to be capable of handling.
In the frequency domain method, the shift corresponds to a rotation of each output data. No buffer is needed in this case, but the technique still has the associated problem of requiring a high resolution rotator. In addition, the output data from the FFT may be generated in a bit-reversed order, meaning that the rotation angle for each consecutive output sample will appear to be more or less random. Thus, a large table to store the angles may result.
In view of the preceding discussion, it is apparent that state-of-the-art methods suffer from a significant overhead in area, latency, and energy consumption. Therefore, it is desirable to provide improved techniques and apparatuses for accomplishing an FFT with a pre-shift/post-rotation of data.